package consistenthash

import (
	"hash/crc32"
	"log"
	"sort"
	"strconv"
)

type Hash func(data []byte) uint32

// 一致性Hash算法的主要数据结构。包含4个成员变量：
// Hash 函数hash
// replicas 虚拟节点倍数
// keys 哈希环
// hashMap 虚拟节点与真实节点的映射表

type Map struct {
	hash     Hash
	replicas int
	keys     []int
	hashMap  map[int]string
}

// 构造函数。允许自定义虚拟节点数和Hash函数

func New(replicas int, fn Hash) *Map {
	m := &Map{
		replicas: replicas,
		hash:     fn,
		hashMap:  make(map[int]string),
	}
	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE
	}

	return m
}

// 添加真实节点的方法。允许传入0或多个真实节点的名称

func (m *Map) Add(keys ...string) {
	for _, key := range keys {
		//对每个真实节点key，对应创建m.replicas个虚拟节点。虚拟节点名称是：strconv.Itoa(i) + key
		// 通过添加编号的方式区分不同虚拟节点。
		for i := 0; i < m.replicas; i++ {
			hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
			log.Printf("key: %s, hashcode: %d\n", key, hash)
			m.keys = append(m.keys, hash)
			m.hashMap[hash] = key
		}
	}

	sort.Ints(m.keys)
}

// 选择节点

func (m *Map) Get(key string) string {
	if len(m.keys) == 0 {
		return ""
	}

	// 计算key的哈希值
	hash := int(m.hash([]byte(key)))
	// 顺时针找到第一个匹配的虚拟节点的下标idx，从m.keys中获取到对应的哈希值
	idx := sort.Search(len(m.keys), func(i int) bool {
		return m.keys[i] >= hash
	})
	// 通过hashMap 映射得到真实的节点
	return m.hashMap[m.keys[idx%len(m.keys)]]
}
